%\subsection{Faster Algorithms via Filtering}
%
%{\bf Outline:} Using filtering, we can improve the running time of connectivity and MST from $\tilde O(m/k^2+n/k)$ to $\tilde O(n/k)$. In fact, this technique also works even when the input is in the {\em worst partition} instead of random partition.  
%
%For certain graph problems we can get a performance boost by sparsifying the graph before applying \Cref{thm:translation}.
%For \mst, we devise the following \emph{filtering} approach:
%Let $G|p_i$ be the (weighted) subgraph of $G$ induced by the nodes mapped to machine $p_i$ including their endpoints (which may be on other machines).
%Note that $G|p_i$ is known to $p_i$ initially.
%We now ``filter'' the edges of the input graph by instructing each machine $p_i$ to locally compute an MST $T_i$ of $G|p_i$.
%For bounding the total number of remaining edges, consider another machine $p_j$ ($j\neq i$).
%By Lemma~\ref{lem:mapping}.(a), each machine has $\tilde O(n/k)$ nodes whp, and thus the number of edges in $T_i$ that have endpoints either in $p_i$ or $p_j$ is $\tilde O(n/k)$.
%Note that $p_i$ and $p_j$ might include distinct inter-machine edges in $T_i$ resp.\ $T_j$.
%To resolve this for each pair $i$, $j$, we instruct the machine with the lower index, say $p_i$, to send its $\tilde O(n/k)$ inter-machine edges to the machine with the higher index, say $p_j$, who replaces the inter-machine edges in $T_j$ between $p_i$ and $p_j$ with the corresponding edges of $T_i$.
%Summing up over the $k-1$ choices for $j$, this shows that $E(T_i) = \tilde O(n)$, and in total, we have the filtered graph $G'$ with $|E(G')|=\tilde O(nk)$.
%
%\begin{lemma} \label{lem:filtering}
%Let $G'$ be the filtered graph of the input graph of $G$.
%Then any MST of $G'$ is an MST of $G$.
%\end{lemma}
%\begin{proof}
%\end{proof}
%
%After this filtering phase, we randomly redistribute the nodes (and the corresponding edges) among the machines.
%To this end, every machine uses (the same) uniform hash function $h : V(G) \rightarrow \{1,\dots,k\}$ that maps nodes to machines, and transmits each assigned node $u$ to machine $h(u)$.
%
%\begin{lemma} \label{lem:filtering2}
%The node redistribution phase takes $\tilde O(n/k)$ rounds.
%\end{lemma}
%\begin{proof}
%\end{proof}
%Along with \Cref{lem:filtering}, this ensures that the filtered graph
%$G'$ satisfies same properties of \Cref{lem:mapping}.
%Finally, we apply the result from \Cref{sec:applications} to yield a bound of $\tilde O(nk /k^2 + \Delta' /k) = \tilde O(n/k)$. 
